package 双端队列;

import 队列.Queue;

import java.util.Iterator;

public class LinkedListQeque<E> implements Deque<E> ,Iterable<E>{//节点
    static class Node<E>{
        Node<E> pre;
        E value;
        Node<E> next;
        public Node(Node<E> pre,E value,Node<E> next){
            this.pre=pre;
            this.value=value;
            this.next=next;
        }
    }
    int capacity;
    int size;
    Node<E> sentinel=new Node<>(null,null,null);//哨兵
    public LinkedListQeque(int capacity){
        this.capacity=capacity;
        sentinel.next=sentinel;
        sentinel.pre=sentinel;
    }
    @Override
    public Iterator<E> iterator() {
       return new Iterator<E>() {
           Node<E> p=sentinel.next;
           @Override
           public boolean hasNext() {
               return p!=sentinel;
           }

           @Override
           public E next() {
               E value=p.value;
               p=p.next;
               return value;
           }
       };
    }

    @Override
    public boolean addFirst(E e) {
        if(isFull()){
            return false;
        }
        Node<E> a=sentinel;
        Node<E> b=sentinel.next;
        Node<E> added=new Node<>(a,e,b);
        a.next=added;
        b.pre=added;
        size++;
        return true;
    }

    @Override
    public boolean offerFirst(E e) {//双向队列的特点
        if(isFull()){
            return false;
        }
        Node<E> a=sentinel.pre;
        Node<E> b=sentinel;
        Node<E> added=new Node<>(a,e,b);
        a.next=added;
        b.pre=added;
        return true;
    }

    @Override
    public E poolFirst() {
        if(isEmpty()){
            return null;
        }
        Node<E> a=sentinel;
        Node<E> removed=sentinel.next;
        Node<E> b=removed.next;
        a.next=b;
        b.pre=a;
        return removed.value;
    }

    @Override
    public E poolLast() {
        if(isEmpty()){
            return null;
        }
        Node<E> b=sentinel;
        Node<E> removed=sentinel.pre;
        Node<E> a=removed.pre;
        a.next=b;
        b.pre=a;
        size--;
        return removed.value;
    }

    @Override
    public E peekFirst() {
        if (isEmpty()){
            return null;
        }
        return sentinel.next.value;
    }

    @Override
    public E peekLast() {
        if(isEmpty()){
            return null;
        }
        return sentinel.pre.value;
    }

    @Override
    public boolean isEmpty() {
        return size==0;
    }

    @Override
    public boolean isFull() {
        return size==capacity;
    }

}

